In a data communication network, a forwarding device (e.g., a data packet switch) directs protocol data units (e.g., data packets) from one network node to another. These data packets may include voice, video, or data information as well as any combination thereof.
To better understand how forwarding devices work within a data communication network, an analogy may be helpful. In many respects, data communication networks are similar to postal delivery systems, with pieces of mail, such as letters or packages, being comparable to the data packets which are transferred within a data communication network. In a postal delivery system, the pieces of mail may be input into the postal delivery system in a variety of ways. Once within the postal delivery system, all of the pieces of mail are collected and transported to nearby processing facilities where the pieces of mail are sorted for further processing. Although each piece of mail will have a unique delivery address, most of the pieces of mail are automatically sorted by a shorter zip code or some other type of routing code. Letters without zip codes must be sorted and processed by hand. Some postal delivery systems also have special forms of encoded delivery addresses, such as Post Office box numbers at a Post Office, which are not recognizable by other postal delivery systems such as Federal Express or United Parcel Service. Regardless of which particular postal delivery system the piece of mail is deposited into, once the mail has been sorted by destination it is routed through additional intermediary processing facilities until it arrives at the local indicated by the destination on the piece of mail. At this point, the zip code or routing code is no longer sufficient to deliver the piece of mail to the intended destination and the local delivery office must further decode the destination address in order to deliver the piece of mail to the intended recipient. In addition to processing pieces of mail for routing the mail to the correct destination, the pieces of mail may go on through several other processing steps. For example, if the piece of mail is going out of the country, it must go through a customs operation in each country. If the national postal delivery system is being used to deliver the piece of mail then it must also be transferred from one national postal delivery system to another. In a private postal delivery system however, this transfer step would not be necessary. The pieces of mail may also be monitored or filtered for such things as mail fraud violation or shipment of hazardous materials.
Data packets are manipulated in a data communication network in a manner similar to that by which pieces of mail are delivered in a postal delivery system. Data packets, for example, are generated by many different types of devices and are placed onto a communication network. Typically, the data packets are concentrated into a forwarding device, such as a local bridge or router, and are then directed by destination over one or more media types (e.g., fiber optic) which are connected to destination devices that could be other larger or smaller bridges or routers. These destination devices then deliver the data packet to its terminal end point (i.e., the end user). Along the way the data communication network may perform filtering and monitoring functions with respect to the data packets.
Just like postal delivery systems have experienced ever increasing volumes of mail which must be delivered, the volume of protocol data units being transferred across computer networks continues to increase as experience is being gained with this new form of communication delivery system and as more and more applications, with more and more expansive means are being developed. In addition, quickly changing technology has made the underlying data transmission resources for computer communication networks relatively inexpensive. Fiber optics, for example, offer data transfer rates in the gigabyte per second range.
The capability or through put of a forwarding device and a computer communication network can be measured either by the number of data packets per second or by the number of bits per second which pass through the forwarding device. The former measure is important because in typical network traffic, the bulk of protocol data units or data packets are small and the critical parameter is how many data packets a forwarding device can handle. If network traffic is weighted by packet size, however, the bulk of the data is carried in large packets. In large bulk data transfers, the second measure of how many bits are being transferred is more important regardless of the number of data packets that are handled. This tension between packet transfer rate versus bit transfer rate is a continuing dichotomy in through put measurements of forwarding devices. Regardless of which through put measure is used, there is a need for through put rates that are substantially higher than the through put rates currently available in forwarding devices.
The existing types of forwarding devices which offer the greatest potential to meet the increasing demand on through put rates are packet switches. Several classes of packet switches exist. Each class differs substantially from the other class of devices, but all may be commonly referred to as packet switches or forwarding devices.
A first class of packet switches is that commonly used in digital telephone exchanges. By analogy, these switches can perform the functions only of a mail carrier picking up and delivering mail along a single route. These switches are intended only to transfer packets among the devices in a single station, such as a telephone exchange. The format of the packet in these systems is chosen to make the hardware in the switch as simple as possible; and this usually means that the packets include fields designed for direct use by the hardware. The capabilities of this class of switches (for example, in such areas as congestion control) are very limited in order to keep the hardware simple.
A second class of packet switches is used in smaller or restricted computer networks, such as X.25 networks. By analogy, these switches are equivalent to the Post Office in a single town with no connection to other Post Offices. In some sense, these switches are little different from the first class of packet switches described above, but there is one substantial difference. The format of the packets (that is, the protocols) handled by the second class of packet switches is much more complex. This greater complexity is necessary because the protocols are designed to work in less restricted environments, and because the packet switches must provide a greater range of services. While the formats interpreted by the first class of switches are chosen for easy implementation in hardware, the data packets handled by this second class of switches are generally intended to be interpreted by software (which can easily and economically handle the greater complexity) and provides the inherit benefit of incremental flexibility in the design of the packet switch.
In a third class of packet switches, the packet protocols are intended to be used in very large data networks having many very dissimilar links (such as a mix of very high speed local area networks (LANs) and low speed long distance point to point lines). Examples of such protocols are the United States designed Transmission Control Protocol/Internetwork Program (TCP/IP), and the International Standards Organization's Internetworking Protocol/Connectionless Network Service (IP/CLNS) protocols.
In addition, this third class of switches (commonly referred to as bridge/routers) often must handle multiple protocols simultaneously. This third class of switches is very similar to the mail processing devices used in the modern postal system. Just as there are many countries, there are many data packet protocols used in computer networks. While a single postal system was once thought to be sufficient to handle mail going anywhere in the world, today several competing systems like United Parcel Service, Federal Express, and the U.S. Postal Service exist to handle the special needs of mail going to every country, state, city, town, and street in the world. Similarly, in computer communication systems, the packet switches are more involved in the carrying of data, and must understand some of the details of each protocol to be able to correctly handle data packets which are being conveyed in that protocol. The routers in this third class of packet switches often have to make fairly complex changes to the data packets as they pass through the packet switch.
It is this latter class of packet switches to which the following detailed description primarily relates. It will be appreciated however, that the detailed description of this invention can readily be applied to the first and second class of switches as well. In current conventional packet switch design, a programmed general purpose processor examines each data packet as it arrives over the network interface and then processes that packet. Packet processing requires assignment of the data packet to an outbound network interface for transmission over the next communications link in the data path. While attempts are being made to build higher speed packet switches, based on this architecture of using general purpose processors, the attempts have not been very successful. One approach is to use faster processors, another is to make the software run faster, and a third is to apply multiple processors to the processing task. All of these approaches fail to meet the increasing performance demands for packet switches for the reasons noted below.
The approach which uses faster processors simply keeps pace with processor dependent (future) demands because the traffic which the packet switch will handle will depend upon the speed of the user processors being used to generate the traffic. Those user processors, like the processors in the packet switches, will increase in speed at more or less the same rate. Accordingly, there is no overall increase in the ability of the future packet switch over present packet switches, relative to traffic load. Furthermore, this approach may be impractical as not being cost-effective for widespread use. For example, two high speed machines, distant from each other, must have intermediate switches which are all equally as powerful; deployment on a large scale of such expensive switches is not likely to be practicable.
The approach which increases the execution rate of the software itself by, for example, removing excess instructions or writing the code in assembly language, leads to a limit beyond which an increase in performance cannot be made. The gains which result are typically small (a few percent) and the engineering costs of such distortions in the software are significant in the long term. This type of assembly code optimization restricts the ability to enhance the software as well as port the software to a different processor platform.
The use of multiple processors to avoid the "processor bottleneck" provides some gains but again has limits. Given a code path to forward a data packet, it is not plausible to split that path into more than a few stages. Typically these stages would involve network input, protocol functions, and network output. The basis for this limitation is the overhead incurred to interface the different processors beyond a limited number of task divisions. That is, after a certain point, the increase in interface overhead outweighs the savings obtained from the additional stage. This is particularly true because of the need to tightly integrate the various components; for example, congestion control at the protocol level requires dose coordination with the output device. Also, the interface overhead costs are made more severe by the complication of the interface which is required.
In general then, the multiprocessor approach is not the answer to substantially increasing the throughput of the packet switching network. This has been borne out by several attempts by technically well-regarded groups to build packet switches using this approach. While aggregate throughput over a large number of interfaces can be obtained, this is, in reality, little different than having a large number of small switches. It has thus far proven implausible to substantially speed up a single stream using the multiprocessing approach.
A need still exists for an improved protocol data unit (i.e., frame, cell, or packet) forwarding system which solves the above-mentioned problems in a manner which can better handle large numbers of input streams, large numbers of output destinations and lines, many different types of communication protocols, and large and small data packets at both high bit throughput rates and high packet throughput rates, while maintaining reasonable costs and complexity.